package com.practice.niuke.new_direct_practice.class17;

import java.util.Arrays;

/**
 * 给定一个数组， 求如果排序之后， 相邻两数的最大差值。 要求时间复杂度O(N)， 且要
 * 求不能用非基于比较的排序。
 */
public class Code01_MaxGap {

    /**
     * 算法流程
     *
     * @param arr 输入数组
     * @return 相邻两数的最大差值
     */
	public static int maxGap(int[] arr) {
	    // 过滤无效输入
		if (arr == null || arr.length < 2) {
			return 0;
		}
		int len = arr.length;
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		// 遍历一遍找出数组中的最小值min和最大值max
		for (int i = 0; i < len; i++) {
			min = Math.min(min, arr[i]);
			max = Math.max(max, arr[i]);
		}
		// 如果min==max，说明数组中只有一种数， 直接返回0
		if (min == max) {
			return 0;
		}

		// 如果数组中不止只有一种数，min~max 一定有range，len个数据，准备len+1个桶
        // 准备len+1个桶
        // hasNum[i] 表示i号桶是否进来过数字
		boolean[] hasNum = new boolean[len + 1];
        // maxs[i] 表示i号桶收集的所有数字中的最大值
		int[] maxs = new int[len + 1];
        // mins[i] 表示i号桶收集的所有数字中的最小值
		int[] mins = new int[len + 1];

        // 桶号
		int bid = 0;
		// 遍历数组
		for (int i = 0; i < len; i++) {
		    // 通过公式计算arr[i]这个数字应该进入几号桶
			bid = bucket(arr[i], len, min, max);
			// arr[i]进桶
			mins[bid] = hasNum[bid] ? Math.min(mins[bid], arr[i]) : arr[i];
			maxs[bid] = hasNum[bid] ? Math.max(maxs[bid], arr[i]) : arr[i];
			hasNum[bid] = true;
		}

		int res = 0;
        // 上一个非空桶的最大值
		int lastMax = maxs[0];
		int i = 1;
		// 遍历所有的非空桶
		for (; i <= len; i++) {
			if (hasNum[i]) {
			    // 当前非空桶的最小值 - 前一个非空桶的最大值，维持最大的。
				res = Math.max(res, mins[i] - lastMax);
				lastMax = maxs[i];
			}
		}
		return res;
	}

    /**
     * 通过公式计算num这个数字应该进入几号桶
     *
     * @param num 需要进桶的数字
     * @param len 原数组的长度
     * @param min 原数组中的最小值
     * @param max 原数组中的最大值
     * @return num这个数字应该进入几号桶
     */
	public static int bucket(long num, long len, long min, long max) {
		return (int) ((num - min) * len / (max - min));
	}

	// for test
	public static int comparator(int[] nums) {
		if (nums == null || nums.length < 2) {
			return 0;
		}
		Arrays.sort(nums);
		int gap = Integer.MIN_VALUE;
		for (int i = 1; i < nums.length; i++) {
			gap = Math.max(nums[i] - nums[i - 1], gap);
		}
		return gap;
	}

	// for test
	public static int[] generateRandomArray(int maxSize, int maxValue) {
		int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
		}
		return arr;
	}

	// for test
	public static int[] copyArray(int[] arr) {
		if (arr == null) {
			return null;
		}
		int[] res = new int[arr.length];
		for (int i = 0; i < arr.length; i++) {
			res[i] = arr[i];
		}
		return res;
	}

	// for test
	public static void main(String[] args) {
		int testTime = 500000;
		int maxSize = 100;
		int maxValue = 100;
		boolean succeed = true;
		for (int i = 0; i < testTime; i++) {
			int[] arr1 = generateRandomArray(maxSize, maxValue);
			int[] arr2 = copyArray(arr1);
			if (maxGap(arr1) != comparator(arr2)) {
				succeed = false;
				break;
			}
		}
		System.out.println(succeed ? "Nice!" : "Fucking fucked!");
	}

}
